﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using ServiceNetworkDesign.Interface;
using ServiceNetworkDesign.Utilities;

namespace ServiceNetworkDesign.Impl
{
    /// <summary>
    /// k短路算法
    /// </summary>
    public  class KShortCutPath:IPath
    {
        private float endFlag;
        public  KShortCutPath(float c)
        {
            this.endFlag = c;
        }
        #region
        //获取k短路
        public List<KPath> GetKPath(List<Node> nodeList, string originID, string destID)
        {
            //ini
            double totalWeight = 0;
            double weight = 0;
            List<Edge> path = null;
            List<string> station = null;
            int m = 1;
            bool flag = false;
            List<KPath> kPath = new List<KPath>();
            path = new List<Edge>();
            station = new List<string>();
            Node curNode = nodeList.Find(p => p.ID == originID);
            while(curNode!=null)
            {
                flag = false;
                foreach (Edge edge in curNode.EdgeList)
                {
                    if(station.Contains(edge.EndNodeID))continue;
                    DShortCutPath shortPath = new DShortCutPath();
                    Path dPath =shortPath.GetPath(nodeList, edge.EndNodeID, destID);
                    if(dPath ==null) return null;

                    weight = totalWeight + edge.Weight + dPath.TotalWeight;
                    //如果弧的终点就是终到站点
                    if((dPath.TotalWeight ==0 )||(weight / dPath.TotalWeight)<endFlag)
                    {
                        //连通图 是回路 条件是边数 > 顶点数-1
                        List<Edge> tmpPath = new List<Edge>();
                        tmpPath.AddRange(path);
                        tmpPath.Add(edge);
                        if(dPath.PassedEdge!=null)tmpPath.AddRange(dPath.PassedEdge);

                        int edgeNum = tmpPath.Distinct().Count();
                        int pointNum = Common.GetNodeIdListByEdges(tmpPath).Count();
  
                        if (edgeNum > pointNum - 1)//含有回路
                        {
                            continue;
                        }
                        else
                        {
                            path.Add(edge);
                            totalWeight += edge.Weight;
                            //run to 4
                            if (edge.EndNodeID != destID)
                            {
                                station.Clear();
                                m = m + 1;
                                curNode = nodeList.Find(p => p.ID == edge.EndNodeID);
                                flag = true;
                                break;
                            }
                            else
                            {
                                KPath curPath = new KPath(path);
                                kPath.Add(curPath);

                                double tmpWeight = path.Last().Weight;
                                path.Remove(path.Last());
                                totalWeight = totalWeight - tmpWeight;
                           
                                station.Add(edge.EndNodeID);
                                break;
                            }
                        }
    
                    }
                }
                if (!flag)   //step3 
                {
                    if (m == 1) break;
                    station.Add(curNode.ID);
                    m = m - 1;
                    //选择下一个相邻节点
                    Edge nextUseEdge =curNode.EdgeList.Find(p => !station.Contains(p.EndNodeID));
                    if (nextUseEdge == null) break;
                    curNode = nodeList.Find(p => p.ID == nextUseEdge.EndNodeID);
                }
            }

            return kPath;
        }
        #endregion
    }
}
